In this paper we study quantum nondeterminism in multiparty communication.There are three (possibly) different types of nondeterminism in quantumcomputation: i) strong, ii) weak with classical proofs, and iii) weak withquantum proofs. Here we focus on the first one. A strong quantumnondeterministic protocol accepts a correct input with positive probability,and rejects an incorrect input with probability 1. In this work we relatestrong quantum nondeterministic multiparty communication complexity to the rankof the communication tensor in the Number-On-Forehead and Number-In-Handmodels. In particular, by extending the definition proposed by de Wolf to {\itnondeterministic tensor-rank} ($nrank$), we show that for any boolean function$f$ when there is no prior shared entanglement between the players, 1) in theNumber-On-Forehead model, the cost is upper-bounded by the logarithm of$nrank(f)$; 2) in the Number-In-Hand model, the cost is lower-bounded by thelogarithm of $nrank(f)$. Furthermore, we show that when the number of playersis $o(\log\log n)$ we have that $NQP\nsubseteq BQP$ for Number-On-Foreheadcommunication.
展开▼
